package com.base.bfs;

import java.util.LinkedList;
import java.util.Queue;

public class UpdateMatrix {
    /**
     * 542. 01 矩阵
     *
     * 给定一个由 0 和 1 组成的矩阵 mat，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
     *
     * 两个相邻元素间的距离为 1
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/01-matrix
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    int[] xx = {1, -1, 0, 0};
    int[] yy = {0, 0, 1, -1};

    public int[][] updateMatrix(int[][] mat) {
        /**
         * 我们所说的「超级零」实际上就是一个「超级源点」。在最短路问题中，如果我们要求多个源点出发的最短路时，一般我们都会建立一个「超级源点」连向所有的源点，用「超级源点」到终点的最短路等价多个源点到终点的最短路
         *
         * 作者：LeetCode-Solution
         * 链接：https://leetcode-cn.com/problems/01-matrix/solution/01ju-zhen-by-leetcode-solution/
         * 来源：力扣（LeetCode）
         * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
         */
        int m = mat.length, n = mat[0].length;
        int[][] distance = new int[m][n];
        Queue<int[]> queue = new LinkedList<int[]>();
        boolean[][] seen = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                    seen[i][j] = true;
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] ints = queue.remove();
            int x = ints[0], y = ints[1];
            for (int i = 0; i < 4; i++) {
                int mx = x + xx[i], my = y + yy[i];
                //判断元素是否越界，以及是否有被访问过；(没有被访问过只可能是1)
                if (mx>-1&&my>-1&&mx<m&&my<n&&!seen[mx][my]){
                        distance[mx][my] = distance[x][y]+1; //等于访问他的哪个元素的距离加1；
                        queue.offer(new int[]{mx,my});//加入到列表中
                        seen[mx][my] = true;//表示被访问
                }
            }

        }
        return distance;

    }




    public static void main(String[] args) {
        UpdateMatrix updateMatrix = new UpdateMatrix();
        int[][] mat = {{0, 0, 0}, {0, 1, 0}, {1, 1, 1}};
        int[][] ints = updateMatrix.updateMatrix(mat);

    }
}
